package 动态规划;

import java.util.PriorityQueue;

public class 丑数 {
//   读不懂题
//    public int nthUglyNumber(int n) {
//         if (n==1)
//             return 1;
//         int num=1,res=2;
//         while (num!=n){
//             if (res%2==0 || res%3==0 || res%5==0)
//                 num++;
//             res++;
//         }
//         return res;
//    }
    //三指针动态规划
public int nthUglyNumber(int n) {
    int[] dp = new int[n + 1];
    dp[1]=1;
    int p2=1,p3=1,p5=1;
    for (int i = 2; i <=n; i++) {
        int nums2=dp[p2]*2,nums3=dp[p3]*3,nums5=dp[p5]*5;
        dp[i]=Math.min(nums2,Math.min(nums3,nums5));
        if (dp[i]==nums2)
            p2++;
        if (dp[i]==nums3)
            p3++;
        if (dp[i]==nums5)
            p5++;
    }
    return dp[n];
}
}
